//
// Created by zhou on 2021/10/30.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int numDecodings(string s) {
        int len=s.length();
        int dp[len];
        if(s[0]=='0')dp[0]=0;
        else dp[0]=1;
        if(len==1)return dp[0];

        if(s[0]>='1'&&s[0]<='2'){
            if(s[1]<='6'&&s[1]>'0'){
                dp[1]=2;
            }
            else if(s[1]=='0')dp[1]=1;
            else dp[1]=1;
        }
        else if(s[0]=='0')dp[1]=0;
        else dp[1]=1;
        if(len==2)return dp[1];


        for(int i=2;i<len;i++){
            if(s[i]>='1'&&s[i]<='6'){
                if(s[i-1]>='1'&&s[i-1]<='2')
                    dp[i]=dp[i-2]+dp[i-1];
                else if(s[i-1]=='0'){

                }
                else dp[i]=dp[i-1];
            }
            else if(s[i]>='7'&&s[i]<='9'){
                if(s[i-1]=='1')dp[i]=dp[i-2]+dp[i-1];
                else dp[i]=dp[i-1];
            }
            else{
                if(s[i-1]>='3'||s[i-1]=='0')dp[i]=0;
                else dp[i]=dp[i-2];
            }

        }
        return dp[len-1];
    }
};
int main(){
    string s="026";
    Solution solution;
    cout<<solution.numDecodings(s);
}
